package com.leetcode.algorithm.y22.m08.w2;

/**
 * 149. 直线上最多的点数
 * 
 * https://leetcode.cn/problems/max-points-on-a-line/
 * 
 * @author jie.deng
 *
 */
class Question0149Solution01 {

	public int maxPoints(int[][] points) {
		int n = points.length;
		int ans = 1;
		for (int i = 0; i < n - 1; i++) {
			int[] x = points[i];
			for (int j = i + 1; j < n; j++) {
				int[] y = points[j];
				int cnt = 2;
				for (int k = j + 1; k < n; k++) {
					int[] p = points[k];
					int s1 = (y[1] - x[1]) * (p[0] - y[0]);
					int s2 = (p[1] - y[1]) * (y[0] - x[0]);
					if (s1 == s2)
						cnt++;
				}
				ans = Math.max(ans, cnt);
			}
		}
		return ans;
	}
}